import java.util.Arrays;

/**
* @description: 828. 统计子串中的唯一字符
* @author hewei
* @date 2022/9/6 14:18
* @version 1.0
*/

public class UniqueLetterString {

    public int uniqueLetterString(String s) {
        int n = s.length();
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        int ans = dp[0];
        int[][] cnt = new int[26][2];
        for (int i = 0; i < 26; i++) {
            Arrays.fill(cnt[i], -1);
        }
        char[] chars = s.toCharArray();
        cnt[chars[0] - 'A'][0] = 0;
        for (int i = 1; i < n; i++) {
            int temp = chars[i] - 'A';
            dp[i] += dp[i - 1];
            if (cnt[temp][0] == -1) {
                dp[i] += i;
                cnt[temp][0] = i;
            } else if (cnt[temp][1] == -1) {
                dp[i] += i - cnt[temp][0] - 1;
                dp[i] -= cnt[temp][0] + 1;
                cnt[temp][1] = i;
            } else {
                dp[i] += i - cnt[temp][1] - 1;
                dp[i] -= cnt[temp][1] - cnt[temp][0];
                cnt[temp][0] = cnt[temp][1];
                cnt[temp][1] = i;
            }
            ans += dp[i];
        }
        return ans;
    }
}
